﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.MergeFindSets
{
    public class RankUnionMFSet<T> : NaiveMergeFindSet<T>
    {
        protected Func<IEnumerable<T>,IMap<T, int>> _createIntegerMap;
        protected IMap<T, int> _rank;
        public RankUnionMFSet(IEnumerable<IEnumerable<T>> sets = null, EqualityComparison<T> equalityComparison = null,
            Func<IEnumerable<T>,IMap<T,T>> createMap = null,
            Func<IEnumerable<T>,IMap<T,Lists.IList<T>>> createMapOfLists=null ,
            Func<IEnumerable<T>,Lists.IList<T>> createList=null,
            Func<IEnumerable<T>,IMap<T,int>> createIntegerMap = null)
        {
            sets = sets ?? Enumerable.Empty<IEnumerable<T>>();
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            _createMap = createMap ?? (items => AlgoritmiaFactory.Maps<T>.Default);
            _createMapOfLists = createMapOfLists ?? (items => AlgoritmiaFactory.Maps<T, Lists.IList<T>>.Default);
            _createList = createList ?? (items => AlgoritmiaFactory.Lists<T>.Default);
            _createIntegerMap = createIntegerMap ?? (items => AlgoritmiaFactory.Maps<T,int>.Default);

            sets = (from set in sets
                    select set.ToList()).ToList();

            var all = Enumerable.Empty<T>();

            foreach(var set in sets)
            {
                all.Concat(set);
            }

            _parent = _createMap(all);
            _rank = _createIntegerMap(all);
            _count = 0;
            foreach (var set in sets)
            {
                List<T> list = set.ToList();
                if (list.Count > 0)
                {
                    _count++;
                    T first = list[0];
                    _parent[first] = first;
                    _rank[first] = 1;
                    for (var i = 1; i < list.Count; i++)
                    {
                        _parent[list[i]] = first;
                        _rank[list[i]] = _rank[first] + 1;
                        //Rank[list[i]] = Rank.Get(list[i], 0) + 1;
                    }
                }
            }
        }

        public override void Add(T item)
        {
            base.Add(item);
            _rank[item] = 1;
        }

        public override void Merge(T item1, T item2)
        {
            T u = Find(item1);
            T v = Find(item2);

            if (!_equalityComparison(u,v))
            {
                _count--;
                if ( _rank[u] < _rank[v])
                {
                    _parent[u] = v;
                }
                else if (_rank[u] > _rank[v])
                {
                    _parent[v] = u;
                }
                else
                {
                    _parent[v] = u;
                    _rank[u]++;
                }
            }
        }

        public override string ToString()
        {
            StringBuilder sb =  new StringBuilder(String.Format("{0} <{1}> [",GetType().Name,typeof(T).Name));
            foreach(var family in this)
            {
                sb.Append(String.Format("[{0}]", string.Join(",", family)));
            }
            sb.Append(" ]");
            return sb.ToString();
        }
    }
}
